package newcoder_exp.baidu;

import java.lang.annotation.Retention;
import java.util.Arrays;

import org.junit.Test;

import utils.ArrayGenerator;

public class Bdu1 {

    //快速排序测试
    public void quickSort(int[] nums, int lo, int hi) {
        if (lo <= hi) {
            int[] p = partion3(nums, lo, hi);
            quickSort(nums, lo, p[0] - 1);
            quickSort(nums, p[1] + 1, hi);
      /*       int p = partion2(nums, lo, hi);
            quickSort(nums, lo, p - 1);
            quickSort(nums, p + 1, hi); */
        } 
    }
        public int[] partion3(int[] nums, int lo, int hi) {
        int i = lo - 1, j = hi + 1, cur = lo;
        int pivot = nums[(int)Math.random() * (hi - lo + 1) + lo];
        while (cur < j) {
            if (nums[cur] == pivot) {
                cur++;
            } else if (nums[cur] > pivot) {
                swap(nums, cur, --j);
            } else {
                swap(nums, ++i, cur++);
            }
        }
        return new int[]{i + 1, j - 1}; //返回pivot的范围
    }

    public int partion2(int[] nums, int left, int right) {
        int lo = left, rand = (int)(Math.random() * (right - left + 1)) + left;
        int sentry = nums[rand], hi = left + 1;
        swap(nums, left, rand);
        while(hi <= right) {
            if (nums[hi] <= sentry) {
                swap(nums, ++lo, hi);
            }
            hi++;
        }
        swap(nums, left, lo);
        return lo;
    }

    public int partion(int[] nums, int left, int right) {
        int lo = left - 1, rand = (int)(Math.random() * (right - left + 1)) + left;
        swap(nums, left, rand);
        int sentry = nums[left];
        while (lo < right) {
            if (nums[lo + 1] > sentry) {
                swap(nums, lo + 1, right--);
            } else {
                lo++;
            }
        }
        swap(nums, left, lo);
        return lo;
    }
    public void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }

    @Test
    public void test() {
        int count = 0;
        for (int i = 0; i < 1000; i++) {
            int[] nums = ArrayGenerator.getArray(20, 10);
            quickSort(nums, 0, 8);
            String res1 = Arrays.toString(nums);
            Arrays.sort(nums);
            String res2 = Arrays.toString(nums);
            if (!res1.equals(res2)) {
                System.out.println(res1);
                count++;
            }
        }

        System.out.println("finished! : " +  count);
    }

    public void QuickSort(int[] nums, int lo, int hi) {
        if (lo < hi) {
            //这里是需要与下面的sentry联动的，因为交换的是hi，因此sentry==nums[hi]
            swap(nums, hi, (int)(Math.random() * (hi - lo + 1) + lo));
            int[] pivot = Partion(nums, lo, hi);
            QuickSort(nums, lo, pivot[0] - 1);
            QuickSort(nums, pivot[1] + 1, hi);
        }
    }

    public int[] Partion(int[] nums, int lo, int hi) {
        int sentry = nums[hi];
        System.out.println(sentry);
        // i:初始时，没有<sentry的区域
        // j:由于最后一位可以确定 == sentry, 因此j起始考察位置为hi - 1, 最后一位留到最后做交换
        // cur:遍历指针
        int i = lo - 1, j = hi, cur = lo;
        while (cur < j) { //遍历到右边界
            if (nums[cur] < sentry) {
                swap(nums, ++i, cur++);
            } else if (nums[cur] > sentry) {
                //换下来的数需要考察【因为j此时停留在未知数上】
                swap(nums, cur, --j);
            } else {
                cur++;
            }
        }
        swap(nums, hi, j);
        //[lo, i]为 < sentry区域， 而由于上面那句交换，此时hi必定是==sentry，因此[i + 1, j]
        return new int[]{i + 1, j};
    }

    @Test
    public void test2() {
        int[] nums = ArrayGenerator.getArray(20, 10);
        nums[8] = nums[9];
        System.out.println(Arrays.toString(nums));
        int[] p = Partion(nums, 0, 9);
        System.out.println(p[0] + "   " + p[1]);
        System.out.println(Arrays.toString(nums));

        int count = 0;
        for (int i = 0; i < 1000; i++) {
            nums = ArrayGenerator.getArray(20, 10);
            quickSort(nums, 0, 8);
            String res1 = Arrays.toString(nums);
            Arrays.sort(nums);
            String res2 = Arrays.toString(nums);
            if (!res1.equals(res2)) {
                System.out.println(res1);
                count++;
            }
        }

        System.out.println("finished! : " +  count);

    }
    public int countDigitOne(int n) {
        int high = n / 10, low = 0, cur = n % 10, d = 1, sum = 0;
        while (high != 0) {
            if (cur == 0) {
                sum += high * d;
            } else if (cur == 1) {
                sum += high * d + low + 1;
            } else {
                sum += (high + 1) * d;
            }

            //参数迭代：
            low = cur * d + low;
            d *= 10;
            cur = high % 10;
            high /= 10;
        }
        if (cur == 1) {
            sum += low + 1;
        } else if (cur > 1) {
            sum += d;
        }
        return sum;
    }

    @Test
    public void test3() {
        System.out.println(countDigitOne(999999999));
    }
}
